public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.longestPalindrome("aaaa"));
    }

    public String longestPalindrome(String s) {
        /**
         * 最长回文子串：解法2：中心扩展算法
         * 算法思想：
         *  以某个元素为基点，向两侧拓展比较，直至越界或不相等*/
        // 1 预处理
        int n = s.length();
        // -边界处理
        if(n == 1) {
            return s;
        }

        // 2 循环处理
        int maxLength = 0;
        int[] maxIndexArray = new int[2];
        for(int i = 0; i < n-1; i++) {
            // -第二层循环用于查找单双中心
            for(int j = i; j <= i+1 && j < n; j++) {
                // -1 拓展
                int l = i;
                int r = j;
                while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                    l--;
                    r++;
                }
                // -2 记录
                if(maxLength < r-l-1) {
                    maxLength = r-l-1;
                    maxIndexArray = new int[]{l+1, r};
                }
            }
        }

        // 3 返回值
        return s.substring(maxIndexArray[0], maxIndexArray[1]);
    }

    public String longestPalindrome1(String s) {
        /**
         * 最长回文子串-解法1：动规
         * 状态表示：
         *  dp[i][j]表示以子串[i,j]是否为回文子串，并规定i<=j
         * 状态转移方程：
         *  if(s.charAt(i) = s.charAt(j)) {
         *      if(i == j || i+1 == j) {
         *          dp[i][j] = true;
         *      } else if(i+1 < j) {
         *          dp[i][j] = dp[i+1][j-1];
         *      }
         *  }
         * 初始化：
         *  无需初始化，并且由于状转中已经进行特判，故无需任何额外处理
         * 填表顺序：
         *  从下岛上，从左到右*/
        // 1 预处理
        int n = s.length();

        // 2 创建dp表
        boolean[][] dp = new boolean[n][n];

        // 3 初始化

        // 4 填表
        int maxLength = -1;
        int[] maxString = new int[2];
        for(int i = n-1; i >= 0; i--) {
            for(int j = i; j < n; j++) {
                if(s.charAt(i) == s.charAt(j)) {
                   if(i == j || i+1 == j) {
                       dp[i][j] = true;
                   } else if(i+1 < j) {
                       dp[i][j] = dp[i+1][j-1];
                   }
                   if(dp[i][j] && j-i+1 > maxLength) {
                       maxLength = j-i+1;
                       maxString = new int[]{i, j+1};
                   }
                }
            }
        }

        // 5 返回值
        return s.substring(maxString[0], maxString[1]);
    }


}
